package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二的幂数组中查询范围内的乘积
 */

public class Code2438 {

    public static void main(String[] args) {
        int n = 15;
        int[][] queries = {{0, 1}, {2, 2}, {0, 3}};
        System.out.println(Arrays.toString(new Code2438().productQueries(n, queries)));
    }

    private static final int MOD = 1_000_000_007;
    private static final int MX = 436;
    private static final int[] pow2 = new int[MX];

    static {
        pow2[0] = 1;
        for (int i = 1; i < MX; i++) {
            pow2[i] = pow2[i - 1] * 2 % MOD;
        }
    }

    public int[] productQueries(int n, int[][] queries) {
        List<Integer> s = new ArrayList<>();
        s.add(0);
        for (; n > 0; n &= n - 1) { // n &= n-1 去掉 n 的最低比特 1
            int e = Integer.numberOfTrailingZeros(n);
            // 直接计算 e 的前缀和
            s.add(s.get(s.size()-1) + e);
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] q = queries[i];
            int sumE = s.get(q[1] + 1) - s.get(q[0]);
            ans[i] = pow2[sumE];
        }
        return ans;
    }
}
